package com.sheng.leetcode.year2022.month09.day20;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/09/20
 *<p>
 * 698. 划分为k个相等的子集<p>
 *<p>
 * 给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。<p>
 *<p>
 * 示例 1：<p>
 * 输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4<p>
 * 输出： True<p>
 * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。<p>
 *<p>
 * 示例 2:<p>
 * 输入: nums = [1,2,3,4], k = 3<p>
 * 输出: false<p>
 *<p>
 * 提示：<p>
 *<p>
 * 1 <= k <= len(nums) <= 16<p>
 * 0 < nums[i] < 10000<p>
 * 每个元素的频率在 [1,4] 范围内<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/partition-to-k-equal-sum-subsets">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0698 {

    @Test
    public void test01() {
//        int[] nums = {4, 3, 2, 3, 5, 2, 1};
//        int k = 4;
//        int[] nums = {1,2,3,4};
//        int k = 3;
//        int[] nums = {1,1,1,1,2,2,2,2};
//        int k = 2;
        int[] nums = {4,4,6,2,3,8,10,2,10,7};
        int k = 4;
        System.out.println(new Solution().canPartitionKSubsets(nums, k));
    }
}
class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        // 计算 nums 数组的总和
        for (int num : nums) {
            sum += num;
        }
        int avg;
        // 总和不能整除 k 时，直接返回 false
        if (sum % k != 0) {
            return false;
        }
        // 获取 avg ，为划分后每个子集的和
        avg = sum / k;
        // 对 nums 数组进行排序
        Arrays.sort(nums);
        // right 为数组的末尾元素
        int right = nums.length - 1;
        // 数组最大的元素大于平均值 avg 时，直接返回 false
        if (nums[right] > avg) {
            return false;
        }
        return dfs(new int[k], k, avg, nums, right);
    }

    public boolean dfs(int[] ints, int k, int avg, int[] nums, int right) {
        if (right < 0) {
            return true;
        }
        int n = nums[right--];
        for (int i = 0; i < ints.length; i++) {
            // 从后往前，想元素中添加值
            if (ints[i] + n <= avg) {
                ints[i] += n;
                // 保证数组 ints 的每个元素都等于 avg
                if (dfs(ints, k, avg, nums, right)) {
                    return true;
                }
                // 回溯
                ints[i] -= n;
            }
            if (ints[i] == 0) {
                return false;
            }
        }
        return false;
    }
}
